package TanXin;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;

class Solution {
    // 贪心算法 -特点是你总能有多个贪心策略
    // 解法是 : 你找一个特别傻的方法解决问题
    // 然后想其他策略, 利用对数器来验证

    public static boolean canPlaceFlowers(int[] flowerbed, int n) {
        // 605 - 给你一个整数数组 flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。
        // 另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？能则返回 true ，不能则返回 false 。
        // 规则-俩多花不能相邻
        int ans =0;
        for (int i = 0; i < flowerbed.length; i++) {
            if (flowerbed[i] == 1){
                i++;
            }else {
                if (i+1 < flowerbed.length && flowerbed[i+1] == 1){
                }else {
                    ans++;
                    i++;
                }
            }
        }
        return ans >= n?true:false;
    }

    public int maxProfit(int prices[]) {
        //121 买卖股票问题
        int minprice = Integer.MAX_VALUE;
        int maxprofit = 0;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < minprice) {
                minprice = prices[i];
            } else if (prices[i] - minprice > maxprofit) {
                maxprofit = prices[i] - minprice;
            }
        }
        return maxprofit;
    }

    public int maxProfitII(int[] prices) {
        if (prices == null){
            return 0;
        }
        int maxprofit=0;
        int minprice = prices[0];
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] - minprice > 0) {
                maxprofit += prices[i] - minprice;
            }
            minprice = prices[i];
        }
        return maxprofit;
    }

    public int arrayPairSum(int[] nums) {
        // 贪心策略: 小的跟小的尽可能在一起
        Arrays.sort(nums);
        int k =0;
        for (int i = 0; i < nums.length; i++) {
            if (i+1 < nums.length){
                k += nums[i];
                i++;
            }
        }
        return k;
    }
    public static int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int j =0;
        int ans =0;
        for (int i = 0; i < g.length && j<s.length; i++) {
            if (s[j] >= g[i]){
                ans++;
                j++;
            }else {
                j++;
                i--;
            }
        }
        return ans;
    }

    public int distributeCandies(int[] candyType) {
        HashSet<Integer> set =new HashSet<>();
        for (Integer k:candyType) {
            set.add(k);
        }
        int len = candyType.length/2;
        return set.size() > len ? len: set.size();
    }
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] left = new int[n];
        for (int i = 0; i < n; i++) {
            if (i > 0 && ratings[i] > ratings[i - 1]) {
                left[i] = left[i - 1] + 1;
            } else {
                left[i] = 1;
            }
        }
        int right = 0, ret = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (i < n - 1 && ratings[i] > ratings[i + 1]) {
                right++;
            } else {
                right = 1;
            }
            ret += Math.max(left[i], right);
        }
        return ret;
    }
    public int longestPalindrome(String s) {
        // 找出可以构成最长回文串的长度
        int[] arr = new int[128];
        for(char c : s.toCharArray()) {
            arr[c]++;
        }
        int count = 0;
        for (int i : arr) {
            count += (i % 2);
        }
        return count == 0 ? s.length() : (s.length() - count + 1);
    }
    //__________________




}